<!doctype html>
<html lang="zh_cn" itemscope itemtype="http://schema.org/Person">
<head>
            <meta charset="utf-8">
        <!-- Site Meta Data -->
        <title>Hihocode #1015 : KMP算法</title>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="description" content="技术博客,涉及Java/PHP/Python/Javascript等,聊聊程序,聊聊生活,聊聊事实,聊聊育儿">
        <meta name="keywords" content="编码经验,技术分享,生活积累,实事评说">
        <meta name="author" content="布丁缘">

        <link rel="shortcut icon" href="">

        <link href='https://fonts.googleapis.com/css?family=Open+Sans:400,600,700' rel='stylesheet' type='text/css'>
        <!-- Style Meta Data -->
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/style.css" type="text/css"/>
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/pygments.css" type="text/css"/>

        <!-- Feed Meta Data -->
            <link href="https://www.ddkiss.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate"
                  title="一个程序员的简单生活 ATOM Feed"/>


    <meta name="keywords" content="">
    <link rel="stylesheet" href="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/default.css">
</head>

<body>
<!-- Sidebar -->
<aside>
    <center><h1><a href="/" style="color:#fff"><img id="avatar" src="/images/avatar.jpg"></a></h1></center>
        <p>一个程序员的简单生活</p>
    <br>
    <nav class="nav">
        <ul class="list-bare">
                <li><a class="nav__link" href="https://www.ddkiss.com/category/chang-yong-ji-qiao.html">常用技巧</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/kai-fa-huan-jing.html">开发环境</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/sheng-huo-dian-di.html">生活点滴</a></li>

                <li><a class="nav__link" href="/pages/books.html">书单</a></li>
                <li><a class="nav__link" href="/pages/movies.html">影单</a></li>
                <li><a class="nav__link" href="/pages/downloads.html">下载</a></li>
                <li><a class="nav__link" href="/pages/about.html">关于我</a></li>


        </ul>
    </nav>


    <form>
      <input type="text"  id="bdcsMain"/>
    </form>

</aside>

<!-- Content -->
<article>
  <main>
    <nav>
      <a href="/">首页</a>
      <a href="/archives.html">归档</a>
      <a href="/categories.html">分类</a>
      <a href="/tags.html">标签</a>
      <a href="/pages/about.html">关于我</a>
    </nav>
  </main>
    <section id="content">
        <article>
            <h2 class="post_title post_detail"><a href="https://www.ddkiss.com/archives/64.html" rel="bookmark"
                                                  title="Permalink to Hihocode #1015 : KMP算法">Hihocode #1015 : KMP算法</a></h2>

            <div class="post_list">
                <span>作者：</span><a href="https://www.ddkiss.com/author/bu-ding-yuan.html">布丁缘</a>
                <span class="post_category">分类：<a href="https://www.ddkiss.com/category/kai-fa-huan-jing.html" rel="bookmark"
                                               title="Permalink to 开发环境">开发环境</a></span>
                <span class="post_date">  时间：2017-10-16 17:41:00</span>

            </div>
            <div class="entry-content blog-post">
                <p>做了一道KMP相关的题，求解字符串中指定子串出现的次数。<a href="http://hihocoder.com/problemset/problem/1015">http://hihocoder.com/problemset/problem/1015</a></p>
<h2>思路</h2>
<p>KMP算法是匹配到子串后(j&gt;=pattern.length)就返回了。本例则是匹配成功后，执行<code>计数+回溯</code>。Hihocode有现成的测试用例，方便进行代码检查。</p>
<h2>代码</h2>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69</pre></div></td><td class="code"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">java.io.BufferedReader</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.io.IOException</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.io.InputStreamReader</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.ArrayList</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.List</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * User: ddkiss.com</span>
<span class="cm"> * Date: 10/16/17 4:26 PM</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>


    <span class="kd">public</span> <span class="kt">int</span><span class="o">[]</span> <span class="nf">getNext</span><span class="o">(</span><span class="n">String</span> <span class="n">pattern</span><span class="o">)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
        <span class="kt">int</span><span class="o">[]</span> <span class="n">next</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span><span class="c1">//next数组长度比pattern多1位</span>
        <span class="n">next</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>

        <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">i</span><span class="o">)</span> <span class="o">==</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">j</span><span class="o">))</span> <span class="o">{</span>
                <span class="n">next</span><span class="o">[++</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">j</span><span class="o">;</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="n">j</span> <span class="o">=</span> <span class="n">next</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
            <span class="o">}</span>
        <span class="o">}</span>
        <span class="k">return</span> <span class="n">next</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kt">int</span> <span class="nf">sameSnippet</span><span class="o">(</span><span class="n">String</span> <span class="n">pattern</span><span class="o">,</span><span class="n">String</span> <span class="n">source</span><span class="o">)</span> <span class="o">{</span>

        <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="kt">int</span><span class="o">[]</span> <span class="n">next</span> <span class="o">=</span> <span class="n">getNext</span><span class="o">(</span><span class="n">pattern</span><span class="o">);</span>
        <span class="kt">int</span> <span class="n">count</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">source</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">source</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">i</span><span class="o">)</span> <span class="o">==</span> <span class="n">pattern</span><span class="o">.</span><span class="na">charAt</span><span class="o">(</span><span class="n">j</span><span class="o">))</span> <span class="o">{</span>
                <span class="n">i</span><span class="o">++;</span>
                <span class="n">j</span><span class="o">++;</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="n">j</span> <span class="o">=</span> <span class="n">next</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
            <span class="o">}</span>

            <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">pattern</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>
                <span class="n">count</span><span class="o">++;</span>
                <span class="n">j</span> <span class="o">=</span> <span class="n">next</span><span class="o">[</span><span class="n">j</span><span class="o">];</span><span class="c1">//回溯</span>
            <span class="o">}</span>
        <span class="o">}</span>
        <span class="k">return</span> <span class="n">count</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="kd">throws</span> <span class="n">IOException</span> <span class="o">{</span>
        <span class="n">Main</span> <span class="n">h</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Main</span><span class="o">();</span>
        <span class="n">BufferedReader</span> <span class="n">br</span> <span class="o">=</span> <span class="k">new</span> <span class="n">BufferedReader</span><span class="o">(</span><span class="k">new</span> <span class="n">InputStreamReader</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">));</span>
        <span class="kt">int</span> <span class="n">arrSize</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">parseInt</span><span class="o">(</span><span class="n">br</span><span class="o">.</span><span class="na">readLine</span><span class="o">());</span>
        <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">counts</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;(</span><span class="n">arrSize</span><span class="o">);</span>
        <span class="k">while</span><span class="o">(</span><span class="n">i</span><span class="o">&lt;</span><span class="n">arrSize</span><span class="o">){</span>
            <span class="n">String</span> <span class="n">pattern</span> <span class="o">=</span> <span class="n">br</span><span class="o">.</span><span class="na">readLine</span><span class="o">();</span>
            <span class="n">String</span> <span class="n">source</span> <span class="o">=</span> <span class="n">br</span><span class="o">.</span><span class="na">readLine</span><span class="o">();</span>
            <span class="n">counts</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">h</span><span class="o">.</span><span class="na">sameSnippet</span><span class="o">(</span><span class="n">pattern</span><span class="o">,</span><span class="n">source</span><span class="o">));</span>
            <span class="n">i</span><span class="o">++;</span>
        <span class="o">}</span>

        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">c</span> <span class="o">:</span> <span class="n">counts</span><span class="o">){</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">c</span><span class="o">);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>
</td></tr></table>
            </div>
            <div class="post_list">
              <div><span>Tags : </span>
              </div>
            </div>
        </article>
        <div id="container"></div>
        <script type="text/javascript" src="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/gitment.min.js"></script>
        <script>
            var gitment = new Gitment({
              owner: 'whusl',
              repo: 'BlogComments',
              oauth: {
                client_id: '621866266817529fba46681653017809',
                client_secret: '14188411740b12ae52159cee9b586bf85cd54125',
              },
            })
            document.getElementById('container').appendChild(gitment.render())
          </script>
    </section>
</article>

<!-- Footer -->
    <footer>
        <p> &copy;2017-2020&nbsp;<a href="http://www.miitbeian.gov.cn/" target="_blank">鄂ICP备17020200号</a>
          Blog powered by <a href="http://getpelican.com/">Pelican</a>
        </p>
    </footer>

    <!-- Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?88c55edaf311dbacac56a16316b04c8b";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>

<script type="text/javascript">(function(){document.write(unescape('%3Cdiv id="bdcs"%3E%3C/div%3E'));var bdcs = document.createElement('script');bdcs.type = 'text/javascript';bdcs.async = true;bdcs.src = 'http://znsv.baidu.com/customer_search/api/js?sid=14490611060029767912' + '&plate_url=' + encodeURIComponent(window.location.href) + '&t=' + Math.ceil(new Date()/3600000);var s = document.getElementsByTagName('script')[0];s.parentNode.insertBefore(bdcs, s);})();</script>

</body>
</html>